package com.test;

/**
 * 快速排序
 *
 * 时间复杂度为o(nlogn) 空间复杂度为o(logn)
 *
 * 最坏O（n^2） 当划分不均匀时候 逆序and排好序都是最坏情况
     最好O（n） 当划分均匀
     partition的时间复杂度: O（n）一共需要logn次partition
 *
 *说明:
 * 选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,
 * 一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
 *
 * Created by abing on 2015/11/26.
 */
public class SuanFaFast {

    public static void main(String[] args){
        int[] aa = {1,4,6,2,5,8,21,43,22,44,33};

        quick(aa);

        for (int a : aa){
            System.out.print(a + " ");
        }
    }

    public static void quick(int[] arr){
        if (arr.length > 0){
            quickSort(arr , 0 ,arr.length - 1);
        }
    }

    public static void quickSort(int[] arr , int low , int high){
        if (low < high){
            int middle = getMiddle(arr , low ,high);    //将list一份为二
            quickSort(arr , low , middle - 1);          //对低字表进行递归排序
            quickSort(arr , middle + 1 , high);         //对高字表进行递归排序
        }
    }

    public static int getMiddle(int[] arr , int low , int high){
        int tmp = arr[low];             //数组的第一个作为中轴
        while (low < high){
            while (low < high && arr[high] >= tmp){
                high--;
            }
            arr[low] = arr[high];       //比中轴小的记录移到低端
            while (low < high && arr[low] <= tmp){
                low++;
            }
            arr[high] = arr[low];       //比中轴大的记录移到高端
        }
        arr[low] = tmp;                 //中轴记录到尾
        return low;                     //返回中轴记录
    }
}
